#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* reverse_list(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;

    while (curr != nullptr) {
        Node* tmp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    return prev;
}

Node* reverse_list_recursive(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    Node* p = reverse_list_recursive(head->next);
    head->next->next = head;
    head->next = nullptr;
    return p;
}